Storing array in PROGMEM

As noted in Ignacio's answer, you can pack your bits of data into bytes and access them via pgm_read_byte() calls. If (for coding convenience, not for efficiency) you prefer to pack the bits into larger units, you can use word and dword access functions, as listed in AVR pgmspace.h documentation. The _near and _far suffixes denote 16 or 32 bit pointers, respectively; for an Uno with its 32K flash memory, _near is always suitable. See PROGMEM documentation at arduino.cc for further discussion.

Here's an example program that accesses and prints data from program memory in 16-bit chunks:

void setup() {
  Serial.begin(115200);         // initialize serial port
}
int k=0;
const uint16_t fnums[] PROGMEM {191, 272, 353, 434, 515, 646, 767, 888};
void loop() {
  uint16_t b = pgm_read_word_near(fnums+k);
  Serial.print(k);  Serial.print(" ");
  Serial.print(b);  Serial.println();
  k = (k+1)%8;
  delay(1000);
}

To pack your 4000 bits of data in the first place, write a C or Python program that runs on a host computer and writes out array definitions that you can cut and paste into a sketch. Here's an example (in Python) that packs bits into bytes:

data = [1,1,0,0,0,1,0,1,0,0,1,0,1,0,1,1,0,0,1,0,0,0,0,0,1,1,0,0,1,0,0,0,0,0,1,0,1,1,1,1,1,1,0,0,0,1,0,1,0,0,0,1,1,1,1,0,0,1,1,1,0,1,1,1,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,1,1,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,1,0,1,0,1,0,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,1,1]

first = 1; byt = 0
for i, b in enumerate(data):
  if i%8==0:
    if first:
       print 'const uint8_t fnums[] PROGMEM {',
       first = 0
    else:
       print '{},'.format(byt),
       byt = 0
  byt = (byt<<1) | b        # add bit into byte being built

print byt<<(8-i%8), '};'

Here is what the program produces:

const uint8_t fnums[] PROGMEM { 197, 43, 32, 200, 47, 197, 30, 119, 153, 37, 180, 117, 48, 218, 214, 212, 170, 262 };

If you want that code to instead pack bits into 16-bit words, change 8 to 16 in four places. Note, the code stores bits in the “bit 0 as MSb and bit 7 as LSb” order mentioned in Ignacio's answer. Thus, data[0] is stored in the high bit of fnums[0], data[8] is stored in the high bit of fnums[1] , and so forth.

Building on the excellent other answers by jwpat7 and Ignacio Vazquez-Abrams, you could conceivably convert your bits into a table using Lua:

data = { 1,1,0,0,0,1,0,1,0,0,1,0,1,0,1,1,0,0,1,0,0,0,0,0,1,1,0,0,1,
         0,0,0,0,0,1,0,1,1,1,1,1,1,0,0,0,1,0,1,0,0,0,1,1,1,1,0,0,1,
         1,1,0,1,1,1,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,1,0,1,1,0,1,0,
         0,0,1,1,1,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,1,1,0,1,
         0,1,1,0,1,1,0,1,0,1,0,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,1,1 }

output = 0
bit = 0

for _, num in ipairs (data) do
  assert (num == 0 or num == 1, "Number must be 0 or 1")
  output = (output * 2) + num
  bit = bit + 1
  if bit >= 8 then
    io.write (output .. ", ")
    output = 0
    bit = 0
  end -- if
end --for

print ""

Output from above:

197, 43, 32, 200, 47, 197, 30, 119, 153, 37, 180, 117, 48, 218, 214, 212, 170, 131,

Now you can make a simple function to pull a particular bit out of PROGMEM:

const byte myTable [] PROGMEM = {
  197, 43, 32, 200, 47, 197, 30, 119, 153, 37, 180, 117, 48, 218, 214, 212, 170, 131, 
  };

bool getBit (const unsigned int which)
  {
  const unsigned int whichByte = which / 8;
  const byte whichBit = which & 0x07;
  return bitRead (pgm_read_byte (&myTable [whichByte]), 7 - whichBit);
  }  // end of getBit

void setup ()
  {
  Serial.begin (115200);
  Serial.println ("Starting");

  for (int i = 0; i < sizeof (myTable) * 8; i++)
    {
    Serial.print (int (getBit (i)));
    Serial.print (", ");
    }
  Serial.println ();
  }  // end of setup

void loop ()
  {
  }  // end of loop

Output from above:

Starting
1,1,0,0,0,1,0,1,0,0,1,0,1,0,1,1,0,0,1,0,0,0,0,0,1,1,0,0,1,0,0,0,0,0,1,0,1,1,1,1,1,1,0,0,0,1,0,1,0,0,0,1,1,1,1,0,0,1,1,1,0,1,1,1,1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,1,1,0,1,1,0,1,0,0,0,1,1,1,0,1,0,1,0,0,1,1,0,0,0,0,1,1,0,1,1,0,1,0,1,1,0,1,0,1,1,0,1,1,0,1,0,1,0,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,1,1,